#include <iostream>
using namespace std;

// 划分函数
int partition(int arr[], int low, int high) {
// 选择最后一个元素作为基准
int pivot = arr[high];
// i 表示小于基准元素的元素的最右边索引
int i = (low - 1);

for (int j = low; j <= high - 1; j++) {
// 将较小的元素移到基准的左边
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// 将基准元素放置在正确的位置上
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;

return (i + 1);
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi 是划分的位置
int pi = partition(arr, low, high);

// 递归地对基准左边和右边的子数组进行排序
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

// 打印数组函数
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}

// 测试示例
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);

std::cout << "排序前的数组为：\n";
printArray(arr, n);
quickSort(arr, 0, n - 1);
std::cout << "排序后的数组为：\n";
printArray(arr, n);

return 0;
}